import time
n = int(input())
people = []
for _ in range(n):
    people.append(int(input()))

def one(N):
    checked = [False for _ in range(N)]
    Honest = [False for _ in range(N)]
    result = []
    def isValid(curr,status):
        # 若没检查则直接放行
        if not checked[(curr-1) %N]: return True
        # 若上上个节点为真判断此节点与上一个节点是否相反
        if (Honest[(curr-1) %N]):
            return Honest[curr] != status
        else: # 若上上个节点为假判断此节点与上一个节点是否相同
            return Honest[curr] == status
        

    def backtracking(index):
        if not False in checked: 
            result.append(Honest[:])
            return
        for status in (True,False):
            if not isValid(index,status):
                continue
            next = (index +1 ) % N
            checked[next] = True
            Honest[next] = status
            backtracking(next)
            checked[next] = False
            Honest[next] = True
    
    
    backtracking(0)
    summm = 0
    for s in result:
        summm += N-sum(s)
    return summm
time1 = time.time()
for pe in people:
    print(one(pe))
print(f"花费{time.time()-time1}秒")

